package com.aikon.wht.paoshan.alg;

import com.google.common.base.Joiner;
import com.google.common.collect.Lists;
import org.apache.commons.lang3.builder.ToStringBuilder;

import java.util.*;

/**
 * 图搜索算法
 * <p>
 * <pre>
 *  0-1-2
 *  | | |
 *  3-4-5
 *    | |
 *    6-7
 * </pre>
 * <p>
 * 邻接矩阵
 * <p>
 * <pre>
 *     0 1 2 3 4 5 6 7
 *  0 [0 1 0 1 0 0 0 0]
 *  1 [1 0 1 0 1 0 0 0]
 *  2 [0 1 0 0 0 1 0 0]
 *  3 [1 0 0 0 1 0 0 0]
 *  4 [0 1 0 1 0 1 1 0]
 *  5 [0 0 1 0 1 0 0 1]
 *  6 [0 0 0 0 1 0 0 1]
 *  7 [0 0 0 0 0 1 1 0]
 * </pre>
 * <p>
 * BFS - 广度优先
 * DFS - 深度优先
 *
 * @author WANGHAITAO273
 */
public class PaoshanOfGraph {

    public static Graph<Integer> initGraph() {
        Node<Integer> node0 = new Node<>(0);

        Node<Integer> node1 = new Node<>(1);

        Node<Integer> node2 = new Node<>(2);

        Node<Integer> node3 = new Node<>(3);

        Node<Integer> node4 = new Node<>(4);

        Node<Integer> node5 = new Node<>(5);

        Node<Integer> node6 = new Node<>(6);

        Node<Integer> node7 = new Node<>(7);

        node0.setNext(node1).setNext(node3);
        node1.setNext(node0).setNext(node2).setNext(node4);
        node2.setNext(node1).setNext(node5);
        node3.setNext(node0).setNext(node4);
        node4.setNext(node1).setNext(node3).setNext(node5);
        node5.setNext(node2).setNext(node4).setNext(node7);
        node6.setNext(node4).setNext(node7);
        node7.setNext(node5).setNext(node6);


        Graph<Integer> graph = new Graph<>(new Node[]{node0, node1, node2, node3, node4, node5, node6, node7});
        return graph;
    }

    public static void main(String[] args) {
        Graph<Integer> graph = initGraph();
        String theWay = bfs(graph, 0, 7);
        System.out.println(theWay);
    }

    public static <T> String bfs(Graph<T> graph, T start, T end) {
        if (start.equals(end)) {
            throw new UnsupportedOperationException("起点与终点相同");
        }
        Node<T> startNode = getNode(graph, start);
        if (startNode.getNext() == null) {
            throw new UnsupportedOperationException("未发现有效路径");
        }

        Node<T> curNode = startNode;
        Ways<T> ways = new Ways<>();

        chooseTheWay(end, curNode, ways);
        return ways.chooseTheWay();
    }

    private static <T> void chooseTheWay(T end, Node<T> curNode, Ways<T> ways) {
        System.out.println("当前节点=" + curNode.getNodeMark());
        List<Node<T>> next = curNode.getNext();
        for (Node<T> nextNode : next) {
            if (end.equals(nextNode.getNodeMark())) {
                ways.add(curNode, nextNode);
                return;
            }
            int distWeight = ways.calcDistWeight(curNode, nextNode);
            if (distWeight < 0) {
                continue;
            }
            if (distWeight > nextNode.getDistWeight() && nextNode.getDistWeight() != 0) {
                continue;
            }

            nextNode.setDistWeight(distWeight);
            ways.add(curNode, nextNode);
            chooseTheWay(end, nextNode, ways);
        }
    }

    private static <T> Node<T> getNode(Graph<T> graph, T nodeMark) {
        for (Node<T> node : graph.getNodes()) {
            if (nodeMark.equals(node.getNodeMark())) {
                return node;
            }
        }
        throw new UnsupportedOperationException("未发现有效节点");
    }


    public static class Ways<T> {
        private List<Way<T>> ways;

        private String chooseTheWay() {
            if (ways == null) {
                throw new UnsupportedOperationException("未发现可用路径");
            }
            Way<T> theWay = ways.get(0);
            int minWeight = theWay.getWeight();
            for (Way<T> way : ways) {
                if (way.weight < minWeight) {
                    theWay = way;
                    minWeight = theWay.getWeight();
                }
            }
            return theWay.toString();
        }


        public void add(Way<T> way) {
            if (ways == null) {
                ways = new ArrayList<>();
            }
            ways.add(way);
        }

        public void add(Node<T> pre, Node<T> cur) {
            if (ways == null) {
                ways = initWays(pre, cur);
                return;
            }
            for (Way<T> way : ways) {
                if (pre.getNodeMark().equals(way.getEnd())) {
                    way.setEnd(cur.getNodeMark());
                    way.getNodeMarks().add(cur.getNodeMark());
                    way.setWeight(way.getWeight() + pre.getWeight(cur.getNodeMark()));
                    continue;
                }
            }

        }


        private List<Way<T>> initWays(Node<T> pre, Node<T> cur) {
            Way<T> way = new Way<>();
            way.setEnd(cur.getNodeMark());
            way.setWeight(pre.getWeight(cur.getNodeMark()));
            way.setNodeMarks(Lists.newArrayList(pre.getNodeMark(), cur.getNodeMark()));
            ways = Lists.newArrayList(way);
            return ways;
        }

        public int calcDistWeight(Node<T> pre, Node<T> cur) {
            int curWeight = pre.getWeight(cur.getNodeMark());
            if (ways == null) {
                ways = initWays(pre, cur);
                return curWeight;
            }
            for (Way<T> way : ways) {
                if (pre.getNodeMark().equals(way.getEnd())) {
                    if (way.getNodeMarks().contains(cur.getNodeMark())) {
                        return -1;
                    }
                    return way.getWeight() + curWeight;
                }
            }
            return Integer.MAX_VALUE;
        }

    }

    public static class Way<T> {

        private T end;

        private int weight;

        private List<T> nodeMarks;

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }

        public T getEnd() {
            return end;
        }

        public void setEnd(T end) {
            this.end = end;
        }

        public List<T> getNodeMarks() {
            return nodeMarks;
        }

        public void setNodeMarks(List<T> nodeMarks) {
            this.nodeMarks = nodeMarks;
        }

        @Override
        public String toString() {
            return new ToStringBuilder(this)
                    .append("weight", weight)
                    .append("nodeMarks", Joiner.on(",").join(nodeMarks))
                    .toString();
        }

    }


    public static class Graph<T> {
        private Node<T>[] nodes;

        public Graph(Node<T>[] nodes) {
            this.nodes = nodes;
        }

        public Node<T>[] getNodes() {
            return nodes;
        }

        public void setNodes(Node<T>[] nodes) {
            this.nodes = nodes;
        }
    }

    public static class NodeWeight<T> {
        private T nodeMark;

        private int weight = 1;

        public T getNodeMark() {
            return nodeMark;
        }

        public void setNodeMark(T nodeMark) {
            this.nodeMark = nodeMark;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }


    public static class Node<T> {

        private T nodeMark;

        private Map<T, Integer> weightMap = new HashMap<>();

        private List<Node<T>> next;

        private int distWeight;

        public Node(T nodeMark) {
            this.nodeMark = nodeMark;
        }

        public Map<T, Integer> getWeightMap() {
            return weightMap;
        }

        public void setWeightMap(Map<T, Integer> weightMap) {
            this.weightMap = weightMap;
        }

        public void setNext(List<Node<T>> next) {
            this.next = next;
        }

        public List<Node<T>> getNext() {
            return next;
        }

        public Node<T> setNext(Node<T> next) {
            if (this.next == null) {
                this.next = Lists.newArrayList(next);
                this.weightMap.put(next.nodeMark, 1);
                return this;
            }
            this.next.add(next);
            this.weightMap.put(next.nodeMark, 1);
            return this;
        }

        public T getNodeMark() {
            return nodeMark;
        }

        public void setNodeMark(T nodeMark) {
            this.nodeMark = nodeMark;
        }


        public int getDistWeight() {
            return distWeight;
        }

        public void setDistWeight(int distWeight) {
            this.distWeight = distWeight;
        }

        public int getWeight(T nodeMark) {
            return weightMap.get(nodeMark);
        }

        @Override
        public String toString() {
            return new ToStringBuilder(this)
                    .append("nodeMark", nodeMark)
                    .append("weightMap", weightMap)
                    .append("distWeight", distWeight)
                    .toString();
        }
    }


}